package Top_Interview_Questions.Tree;


import Top_Interview_Questions.Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/2 18:39
 * <p>
 * 功能描述:
 */
public class _0108 {

    public static void main(String[] args) {
        _0108 test = new _0108();
        int[] nums = new int[]{-10,-3,0,5,9};
        test.sortedArrayToBST(nums);
    }


    /*-----------------------------------------递归-------------------------------------------*/

    /**
     * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
     * solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-24/
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        return sortedArrayToBST(nums, 0, nums.length);
    }

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start == end) {
            return null;
        }
        int mid = (start + end) >>> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid);
        root.right = sortedArrayToBST(nums, mid + 1, end);

        return root;
    }

    /*----------------------------------------------------------------------------------------*/
}
